Data structures are generally defined as ways of storing and organizing data in a computer that allows the data to be used efficiently. Recent trends in data storage have led to increased storage of the data structures in non-volatile memories. As such, there has been a growing need to ensure that the data structure is never left in an inconsistent state. However, current processors do not provide the necessary hooks to guarantee data ordering for writes from being flushed from the processor cache to memory.
Conventional processors support a memory fence (mfence) instruction, which guarantees that all memory reads and writes issued before it are completed and globally visible before any reads or writes after the mfence instruction, the visibility is only with respect to the processor's caches. Executing an mfence instruction, however, does not guarantee that all memory writes are propagated to main memory or that the ordering of writes is maintained. One option is to flush all of the cache contents using the write-back and invalidate cache (wbinvd) instruction, however, this significantly harms performance as it also impacts the instruction cache, read-only data, as well as data unrelated to the data structure.
In addition, in conventional mechanisms for updating data structures, a memory controller can reorder writes at a cache line granularity, and data structures are likely to be corrupted in the face of power or software failures. As such, conventional processors and memory controllers are typically unable to guarantee that data structures will not be left in inconsistent states.